package 树与图.字典树;

/**
 * 236. 二叉树的最近公共祖先
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 *
 * 问题描述：
 *  给定一棵二叉树和两个节点 p 和 q，找到它们的最近公共祖先（LCA）。
 *  最近公共祖先定义为：对于树中的两个节点 p 和 q，最低的公共祖先节点是同时包含 p 和 q 作为后代的最深节点（允许节点本身是后代）。
 *
 *  核心思路：
 *    利用后续遍历的特性（左右根），从底向上遍历二叉树，递归过程中，如果当前子树同时包含p和q，则返回当前节点；
 *    如果仅包含其中一个节点，则返回该节点；否则返回null；
 *  关键点：
 *    1：递归终止条件：
 *      - 当前节点为null，则返回null；
 *      - 当前节点为p 或者 q，则返回当前节点;
 *    2: 递归逻辑：
 *     - 递归左子树和右子树，分别为left 和 right；
 *     - 若left 和 right 都不为null，则说明当前节点为LCAN，返回当前节点；
 *     - 如果其中一个不为空，返回非空的结果（向上传递可能存在的LCA）
 */
public class L_236 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root ==p || root == q){
            return root;
        }
        // 后续遍历的特性，左右根
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // 判断条件
        if(left != null && right != null){
            return root;
        }
        // 左右子树有一个为空，则返回非空的子树
        return left != null ? left : right;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
